/* Find and resolve or report look-ahead conflicts for bison,
   Copyright (C) 1984, 1989 Free Software Foundation, Inc.

This file is part of Bison, the GNU Compiler Compiler.

Bison is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

Bison is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with Bison; see the file COPYING.  If not, write to
the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */



#ifdef _AIX
#pragma alloca
#endif
#include <stdio.h>
#include <malloc.h>
#include "system.h"
#include "machine.h"
#include "new.h"
#include "files.h"
#include "gram.h"
#include "state.h"



extern char **tags;
extern int tokensetsize;
extern char *consistent;
extern short *accessing_symbol;
extern shifts **shift_table;
extern unsigned *LA;
extern short *LAruleno;
extern short *lookaheads;
extern int verboseflag;

void set_conflicts();
void resolve_sr_conflict();
void flush_shift();
void log_resolution();
void total_conflicts();
void count_sr_conflicts();
void count_rr_conflicts();

char any_conflicts;
char *conflicts;
errs **err_table;
int expected_conflicts;


static unsigned *shiftset;
static unsigned *lookaheadset;
static int src_total;
static int rrc_total;
static int src_count;
static int rrc_count;


void
initialize_conflicts()
{
    register int i;
/*  register errs *sp; JF unused */

    conflicts = NEW2(nstates, char);
    shiftset = NEW2(tokensetsize, unsigned);
    lookaheadset = NEW2(tokensetsize, unsigned);

    err_table = NEW2(nstates, errs *);

    any_conflicts = 0;

    for (i = 0; i < nstates; i++)
    set_conflicts(i);
}


void
set_conflicts(state)
int state;
{
    register int i;
    register int k;
    register shifts *shiftp;
    register unsigned *fp2;
    register unsigned *fp3;
    register unsigned *fp4;
    register unsigned *fp1;
    register int symbol;

    if (consistent[state]) return;

    for (i = 0; i < tokensetsize; i++)
    lookaheadset[i] = 0;

    shiftp = shift_table[state];
    if (shiftp)
    {
        k = shiftp->nshifts;
        for (i = 0; i < k; i++)
        {
            symbol = accessing_symbol[shiftp->shifts[i]];
            if (ISVAR(symbol)) break;
            SETBIT(lookaheadset, symbol);
        }
    }

    k = lookaheads[state + 1];
    fp4 = lookaheadset + tokensetsize;

/* loop over all rules which require lookahead in this state */
/* first check for shift-reduce conflict, and try to resolve using precedence  */

    for (i = lookaheads[state]; i < k; i++)
    if (rprec[LAruleno[i]])
    {
        fp1 = LA + i * tokensetsize;
        fp2 = fp1;
        fp3 = lookaheadset;

        while (fp3 < fp4)
        {
            if (*fp2++ & *fp3++)
            {
                resolve_sr_conflict(state, i);
                break;
            }
        }
    }

/* loop over all rules which require lookahead in this state */
/* Check for conflicts not resolved above.  */

    for (i = lookaheads[state]; i < k; i++)
    {
        fp1 = LA + i * tokensetsize;
        fp2 = fp1;
        fp3 = lookaheadset;

        while (fp3 < fp4)
        {
            if (*fp2++ & *fp3++)
            {
                conflicts[state] = 1;
                any_conflicts = 1;
            }
        }

        fp2 = fp1;
        fp3 = lookaheadset;

        while (fp3 < fp4)
            *fp3++ |= *fp2++;
    }
}



/* Attempt to resolve shift-reduce conflict for one rule
by means of precedence declarations.
It has already been checked that the rule has a precedence.
A conflict is resolved by modifying the shift or reduce tables
so that there is no longer a conflict.  */



void
resolve_sr_conflict(state, lookaheadnum)
int state;
int lookaheadnum;
{
    register int i;
    register int mask;
    register unsigned *fp1;
    register unsigned *fp2;
    register int redprec;
/* Extra parens avoid errors on Ultrix 4.3.  */
    errs *errp = (errs *) alloca ((sizeof(errs) + ntokens * sizeof(short)));
    short *errtokens = errp->errs;

/* find the rule to reduce by to get precedence of reduction  */
    redprec = rprec[LAruleno[lookaheadnum]];

    mask = 1;
    fp1 = LA + lookaheadnum * tokensetsize;
    fp2 = lookaheadset;
    for (i = 0; i < ntokens; i++)
    {
        if ((mask & *fp2 & *fp1) && sprec[i])
/* Shift-reduce conflict occurs for token number i
	   and it has a precedence.
	   The precedence of shifting is that of token i.  */


        {
            if (sprec[i] < redprec)
            {
                if (verboseflag) log_resolution(state, lookaheadnum, i, "reduce");
                *fp2 &= ~mask;  /* flush the shift for this token */
                flush_shift(state, i);
            }
            else if (sprec[i] > redprec)
            {
                if (verboseflag) log_resolution(state, lookaheadnum, i, "shift");
                *fp1 &= ~mask;  /* flush the reduce for this token */
            }
            else
            {
/* Matching precedence levels.
		 For left association, keep only the reduction.
		 For right association, keep only the shift.
		 For nonassociation, keep neither.  */



                switch (sassoc[i])
                {

                case RIGHT_ASSOC:
                    if (verboseflag) log_resolution(state, lookaheadnum, i, "shift");
                    break;

                case LEFT_ASSOC:
                    if (verboseflag) log_resolution(state, lookaheadnum, i, "reduce");
                    break;

                case NON_ASSOC:
                    if (verboseflag) log_resolution(state, lookaheadnum, i, "an error");
                    break;
                }

                if (sassoc[i] != RIGHT_ASSOC)
                {
                    *fp2 &= ~mask;  /* flush the shift for this token */
                    flush_shift(state, i);
                }
                if (sassoc[i] != LEFT_ASSOC)
                {
                    *fp1 &= ~mask;  /* flush the reduce for this token */
                }
                if (sassoc[i] == NON_ASSOC)
                {
/* Record an explicit error for this token.  */
                    *errtokens++ = i;
                }
            }
        }

        mask <<= 1;
        if (mask == 0)
        {
            mask = 1;
            fp2++;  fp1++;
        }
    }
    errp->nerrs = (short)(errtokens - errp->errs);
    if (errp->nerrs)
    {
/* Some tokens have been explicitly made errors.  Allocate
	 a permanent errs structure for this state, to record them.  */


        i = (int)((char *) errtokens - (char *) errp);
        err_table[state] = (errs *) xmalloc ((unsigned int)i);
        bcopy (errp, err_table[state], i);
    }
    else
        err_table[state] = 0;
}



/* turn off the shift recorded for the specified token in the specified state.
Used when we resolve a shift-reduce conflict in favor of the reduction.  */



void
flush_shift(state, token)
int state;
int token;
{
    register shifts *shiftp;
    register int k, i;
/*  register unsigned symbol; JF unused */

    shiftp = shift_table[state];

    if (shiftp)
    {
        k = shiftp->nshifts;
        for (i = 0; i < k; i++)
        {
            if (shiftp->shifts[i] && token == accessing_symbol[shiftp->shifts[i]])
                (shiftp->shifts[i]) = 0;
        }
    }
}


void
log_resolution(state, LAno, token, resolution)
int state, LAno, token;
char *resolution;
{
    fprintf(foutput,
        "Conflict in state %d between rule %d and token %s resolved as %s.\n",
        state, LAruleno[LAno], tags[token], resolution);
}


void
conflict_log()
{
    register int i;

    src_total = 0;
    rrc_total = 0;

    for (i = 0; i < nstates; i++)
    {
        if (conflicts[i])
        {
            count_sr_conflicts(i);
            count_rr_conflicts(i);
            src_total += src_count;
            rrc_total += rrc_count;
        }
    }

    total_conflicts();
}


void
verbose_conflict_log()
{
    register int i;

    src_total = 0;
    rrc_total = 0;

    for (i = 0; i < nstates; i++)
    {
        if (conflicts[i])
        {
            count_sr_conflicts(i);
            count_rr_conflicts(i);
            src_total += src_count;
            rrc_total += rrc_count;

            fprintf(foutput, "State %d contains", i);

            if (src_count == 1)
                fprintf(foutput, " 1 shift/reduce conflict");
            else if (src_count > 1)
                fprintf(foutput, " %d shift/reduce conflicts", src_count);

            if (src_count > 0 && rrc_count > 0)
                fprintf(foutput, " and");

            if (rrc_count == 1)
                fprintf(foutput, " 1 reduce/reduce conflict");
            else if (rrc_count > 1)
                fprintf(foutput, " %d reduce/reduce conflicts", rrc_count);

            putc('.', foutput);
            putc('\n', foutput);
        }
    }

    total_conflicts();
}


void
total_conflicts()
{
    extern int fixed_outfiles;

    if (src_total == expected_conflicts && rrc_total == 0)
        return;

    if (fixed_outfiles)
    {
/* If invoked under the name `yacc', use the output format
	 specified by POSIX.  */


        fprintf(stderr, "conflicts: ");
        if (src_total > 0)
            fprintf(stderr, " %d shift/reduce", src_total);
        if (src_total > 0 && rrc_total > 0)
            fprintf(stderr, ",");
        if (rrc_total > 0)
            fprintf(stderr, " %d reduce/reduce", rrc_total);
        putc('\n', stderr);
    }
    else
    {
        fprintf(stderr, "%s contains", infile);

        if (src_total == 1)
            fprintf(stderr, " 1 shift/reduce conflict");
        else if (src_total > 1)
            fprintf(stderr, " %d shift/reduce conflicts", src_total);

        if (src_total > 0 && rrc_total > 0)
            fprintf(stderr, " and");

        if (rrc_total == 1)
            fprintf(stderr, " 1 reduce/reduce conflict");
        else if (rrc_total > 1)
            fprintf(stderr, " %d reduce/reduce conflicts", rrc_total);

        putc('.', stderr);
        putc('\n', stderr);
    }
}


void
count_sr_conflicts(state)
int state;
{
    register int i;
    register int k;
    register int mask;
    register shifts *shiftp;
    register unsigned *fp1;
    register unsigned *fp2;
    register unsigned *fp3;
    register int symbol;

    src_count = 0;

    shiftp = shift_table[state];
    if (!shiftp) return;

    for (i = 0; i < tokensetsize; i++)
    {
        shiftset[i] = 0;
        lookaheadset[i] = 0;
    }

    k = shiftp->nshifts;
    for (i = 0; i < k; i++)
    {
        if (! shiftp->shifts[i]) continue;
        symbol = accessing_symbol[shiftp->shifts[i]];
        if (ISVAR(symbol)) break;
        SETBIT(shiftset, symbol);
    }

    k = lookaheads[state + 1];
    fp3 = lookaheadset + tokensetsize;

    for (i = lookaheads[state]; i < k; i++)
    {
        fp1 = LA + i * tokensetsize;
        fp2 = lookaheadset;

        while (fp2 < fp3)
            *fp2++ |= *fp1++;
    }

    fp1 = shiftset;
    fp2 = lookaheadset;

    while (fp2 < fp3)
        *fp2++ &= *fp1++;

    mask = 1;
    fp2 = lookaheadset;
    for (i = 0; i < ntokens; i++)
    {
        if (mask & *fp2)
            src_count++;

        mask <<= 1;
        if (mask == 0)
        {
            mask = 1;
            fp2++;
        }
    }
}


void
count_rr_conflicts(state)
int state;
{
    register int i;
    register int j;
    register int count;
    register unsigned mask;
    register unsigned *baseword;
    register unsigned *wordp;
    register int m;
    register int n;

    rrc_count = 0;

    m = lookaheads[state];
    n = lookaheads[state + 1];

    if (n - m < 2) return;

    mask = 1;
    baseword = LA + m * tokensetsize;
    for (i = 0; i < ntokens; i++)
    {
        wordp = baseword;

        count = 0;
        for (j = m; j < n; j++)
        {
            if (mask & *wordp)
                count++;

            wordp += tokensetsize;
        }

        if (count >= 2) rrc_count++;

        mask <<= 1;
        if (mask == 0)
        {
            mask = 1;
            baseword++;
        }
    }
}


void
print_reductions(state)
int state;
{
    register int i;
    register int j;
    register int k;
    register unsigned *fp1;
    register unsigned *fp2;
    register unsigned *fp3;
    register unsigned *fp4;
    register int rule;
    register int symbol;
    register unsigned mask;
    register int m;
    register int n;
    register int default_LA;
    register int default_rule;
    register int cmax;
    register int count;
    register shifts *shiftp;
    register errs *errp;
    int nodefault = 0;

    for (i = 0; i < tokensetsize; i++)
    shiftset[i] = 0;

    shiftp = shift_table[state];
    if (shiftp)
    {
        k = shiftp->nshifts;
        for (i = 0; i < k; i++)
        {
            if (! shiftp->shifts[i]) continue;
            symbol = accessing_symbol[shiftp->shifts[i]];
            if (ISVAR(symbol)) break;
/* if this state has a shift for the error token,
	     don't use a default rule.  */


            if (symbol == error_token_number) nodefault = 1;
            SETBIT(shiftset, symbol);
        }
    }

    errp = err_table[state];
    if (errp)
    {
        k = errp->nerrs;
        for (i = 0; i < k; i++)
        {
            if (! errp->errs[i]) continue;
            symbol = errp->errs[i];
            SETBIT(shiftset, symbol);
        }
    }

    m = lookaheads[state];
    n = lookaheads[state + 1];

    if (n - m == 1 && ! nodefault)
    {
        default_rule = LAruleno[m];

        fp1 = LA + m * tokensetsize;
        fp2 = shiftset;
        fp3 = lookaheadset;
        fp4 = lookaheadset + tokensetsize;

        while (fp3 < fp4)
            *fp3++ = *fp1++ & *fp2++;

        mask = 1;
        fp3 = lookaheadset;

        for (i = 0; i < ntokens; i++)
        {
            if (mask & *fp3)
                fprintf(foutput, "    %-4s\t[reduce using rule %d (%s)]\n",
                    tags[i], default_rule, tags[rlhs[default_rule]]);

            mask <<= 1;
            if (mask == 0)
            {
                mask = 1;
                fp3++;
            }
        }

        fprintf(foutput, "    $default\treduce using rule %d (%s)\n\n",
            default_rule, tags[rlhs[default_rule]]);
    }
    else if (n - m >= 1)
    {
        cmax = 0;
        default_LA = -1;
        fp4 = lookaheadset + tokensetsize;

        if (! nodefault)
            for (i = m; i < n; i++)
        {
            fp1 = LA + i * tokensetsize;
            fp2 = shiftset;
            fp3 = lookaheadset;

            while (fp3 < fp4)
                *fp3++ = *fp1++ & ( ~ (*fp2++));

            count = 0;
            mask = 1;
            fp3 = lookaheadset;
            for (j = 0; j < ntokens; j++)
            {
                if (mask & *fp3)
                    count++;

                mask <<= 1;
                if (mask == 0)
                {
                    mask = 1;
                    fp3++;
                }
            }

            if (count > cmax)
            {
                cmax = count;
                default_LA = i;
                default_rule = LAruleno[i];
            }

            fp2 = shiftset;
            fp3 = lookaheadset;

            while (fp3 < fp4)
                *fp2++ |= *fp3++;
        }

        for (i = 0; i < tokensetsize; i++)
        shiftset[i] = 0;

        if (shiftp)
        {
            k = shiftp->nshifts;
            for (i = 0; i < k; i++)
            {
                if (! shiftp->shifts[i]) continue;
                symbol = accessing_symbol[shiftp->shifts[i]];
                if (ISVAR(symbol)) break;
                SETBIT(shiftset, symbol);
            }
        }

        mask = 1;
        fp1 = LA + m * tokensetsize;
        fp2 = shiftset;
        for (i = 0; i < ntokens; i++)
        {
            int defaulted = 0;

            if (mask & *fp2)
                count = 1;
            else
                count = 0;

            fp3 = fp1;
            for (j = m; j < n; j++)
            {
                if (mask & *fp3)
                {
                    if (count == 0)
                    {
                        if (j != default_LA)
                        {
                            rule = LAruleno[j];
                            fprintf(foutput, "    %-4s\treduce using rule %d (%s)\n",
                                tags[i], rule, tags[rlhs[rule]]);
                        }
                        else defaulted = 1;

                        count++;
                    }
                    else
                    {
                        if (defaulted)
                        {
                            rule = LAruleno[default_LA];
                            fprintf(foutput, "    %-4s\treduce using rule %d (%s)\n",
                                tags[i], rule, tags[rlhs[rule]]);
                            defaulted = 0;
                        }
                        rule = LAruleno[j];
                        fprintf(foutput, "    %-4s\t[reduce using rule %d (%s)]\n",
                            tags[i], rule, tags[rlhs[rule]]);
                    }
                }

                fp3 += tokensetsize;
            }

            mask <<= 1;
            if (mask == 0)
            {
                mask = 1;
/* We tried incrementing just fp1, and just fp2; both seem wrong.
		 It seems necessary to increment both in sync.  */


                fp1++;
                fp2++;
            }
        }

        if (default_LA >= 0)
        {
            fprintf(foutput, "    $default\treduce using rule %d (%s)\n",
                default_rule, tags[rlhs[default_rule]]);
        }

        putc('\n', foutput);
    }
}


void
finalize_conflicts()
{
    FREE(conflicts);
    FREE(shiftset);
    FREE(lookaheadset);
}
